In computer science, there are a number of data structures that have been developed to represent spatial data. For example, the quadtree data structure has been utilized to represent graphical data structures. A quadtree tree is a two dimensional data structure that represents objects hierarchically. Each child node of a quadtree represents a quadrant of a parent node.
FIG. 1 graphically depicts exemplary quadtree 100 that includes nodes 101, 102, 103, and 104 which are the first quadrants (spatial subdivisions) of the data structure. Node 103 is empty and, hence, does not contain any further child nodes. Accordingly, it is unnecessary to represent further spatial subdivisions of node 103. A special code, character, or pointer-value may be used to implement node 103 to indicate that node 103 is an empty node. Nodes 101, 102, and 104 are further subdivided. Specifically, the upper left and lower right quadrants of each of nodes 101, 102, and 104 are occupied. Each of the parent nodes (nodes 101, 102, and 104) may be implemented as a set of pointers (or other suitable characters or codes) to data structures that represent the respective child nodes. The empty child nodes of nodes 101, 102, and 104 may be represented by the same special code, character, or pointer-value that is used to implement node 103. The non-empty child nodes (nodes 105-110) of the parent nodes (nodes 101, 102, and 104) may be represented in several ways. The non-empty child nodes may be represented as a pointer to a data structure that represents the contents of the child nodes. Alternatively, the non-empty child nodes may be represented by a suitable character or code that represents the contents of the child node. The implementation of the non-empty leaf nodes may depend upon the complexity of the contents of the leaf nodes. If the contents of the leaf nodes are limited (e.g., restricted to a small range of colors if the quadtree represents a graphical image), it may be more memory efficient to utilize a character or code as opposed to a pointer to another data structure.
An octree is a generalization of the tree structure to three-dimensional space. Each node (“cube”) may be subdivided into eight further nodes. FIG. 2 graphically depicts node 200 of the octree (which represents the entire spatial region associated with the octree), the first subdivided level 201 of the octree (which contains 8 nodes), and the second subdivided level 202 of the octree (which contains 64 nodes). In the same manner as a quadtree tree, leaf nodes may be identified at multiple levels of the same octree and a parent node may be implemented as a set of pointers to the respective child nodes of the parent node.
Furthermore, a graph is another data structure that is well-known in computer science. A graph is a set of nodes and a set of edges where an edge is defined by the a pair of nodes it connects. A directed graph is a graph where the order of the nodes in an edge is relevant (e.g., the graph is traversed in a particular direction by an associated algorithm). Acyclic means there are no cycles in the graph, i.e., no path through the graph can traverse the same node more than once. FIG. 3 depicts an example of a directed acyclic graph (DAG) 300 according to the prior art. DAG 300 begins at node A and continues to node B and then to node C. At node C, two edges may be traversed. At node C, an edge may be traversed by continuing to node E where the graph terminates. Also, at node C, another edge may be traversed by continuing to node D. From node D, DAG 300 continues to node E where the graph terminates.
In one unusual known application, the binary quadtree data structure and the directed acyclic graph data structure were combined. Specifically, the adaptation of the “life algorithm” developed by Bill Gosper utilized this combination to represent the evolution of “life” in a finite two-dimensional space. The life algorithm begins by defining the presence or absence of life in each spatial subdivision of the finite two-dimensional space where a logical zero represents the absence of life and a logical one represents the presence of life. The life algorithm operates by determining whether existing life will continue or cease and whether life in each empty subdivision will develop. The algorithm makes these determinations upon the basis of density of life in adjacent spatial subdivisions. In essence, overcrowding leads to cessation of life while a certain amount of density is required for development. The life algorithm operates by iterating the determination of whether life will continue and whether life will develop. The advantage of the combination of the binary quadtree data structure and the DAG data structure is that similar patterns of “life” that arise in subsequent iterations do not require recalculation. Accordingly, the combination data structure simplifies the processing of the life algorithm.